Search for: All records

Abstract We give Hoeffding- and Bernstein-type concentration inequalities for the largest eigenvalue of sums of random matrices arising from a Markov chain. We consider time-dependent matrix-valued functions on a general state space, generalizing previous results that had only considered Hoeffding-type inequalities, and only for time-independent functions on a finite state space. In particular, we study a kind of non-commutative moment generating function, provide tight bounds on this object and use a method of Garg et al. (A matrix expander Chernoff bound. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 1102–1114, New York, NY, USA, 2018. Association for Computing Machinery) to turn this into tail bounds. Our proof proceeds spectrally, bounding the norm of a certain perturbed operator. In the process we make an interesting connection to dynamical systems and Banach space theory to prove a crucial result on the limiting behaviour of our moment generating function that may be of independent interest. 

Abstract We prove moderate deviations bounds for the lower tail of the number of odd cycles in a random graph. We show that the probability of decreasing triangle density by , is whenever . These complement results of Goldschmidt, Griffiths, and Scott, who showed that for , the probability is . That is, deviations of order smaller than behave like small deviations, and deviations of order larger than behave like large deviations. We conjecture that a sharp change between the two regimes occurs for deviations of size , which we associate with a single large negative eigenvalue of the adjacency matrix becoming responsible for almost all of the cycle deficit. We give analogous results for the ‐cycle density, for all odd . Our results can be interpreted as finite size effects in phase transitions in constrained random graphs.